package cn.handong.tool.algorithm.排序;

import javafx.scene.effect.Effect;
import org.junit.Test;
import org.springframework.data.redis.core.ReactiveRedisCallback;

import java.util.Arrays;

public class SortTest {
    @Test
    public void bubbleSort(){   // 从小到大
        int[] nums = {5,9,2,3,1};
        int temp;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {// 每一轮，最大值放到最后
                if (nums[j] > nums[j + 1]){ // 索引 j j+1 互换
                    temp = nums[j + 1];
                    nums[j + 1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    @Test
    public void test(){
        int[] nums = {5,9,2,3,1,8,2};
        int[] ints = mergeSort(nums);
        System.out.println(Arrays.toString(ints));
    }

    // 归并排序
    public static int[] mergeSort(int[] nums){
//        int[] nums = {5,9,2,3,1,8,2};
        if (nums.length <= 1) return nums;
        int len = nums.length;
        int mid = len / 2;
        return merge(mergeSort(Arrays.copyOfRange(nums,0,mid)),mergeSort(Arrays.copyOfRange(nums,mid,len)));
    }
    public static int[] merge(int[] left, int[] right){
        int[] res = new int[left.length + right.length];
        int i = 0, j = 0;
        for (int index = 0; index < res.length; index++) {
            if (i >= left.length){
                res[index] = right[j++];
            }else if (j >= right.length){
                res[index] = left[i++];
            }else if (left[i] > right[j]){
                res[index] = right[j++];
            }else {
                res[index] = left[i++];
            }
        }
        return res;
    }

    @Test
    public void testQuickSort(){
        int[] nums = {5,9,2,3,1,8,7};
        quickSort(nums,0,nums.length-1);
        System.out.println(Arrays.toString(nums));
    }

    // 快速排序
    public static void quickSort(int[] nums,int low,int high){
        if (low >= high){
            return;
        }
        int mid = getMid(nums,low,high);
        quickSort(nums,low,mid - 1);
        quickSort(nums,mid+1,high);
    }

    public static int getMid(int[] nums,int low,int high){
        int tem = nums[low];  // 设为基准值
        while (low < high){
            while (high > low && tem <= nums[high]){
                high--;
            }
            nums[low] = nums[high];
            while (high > low && tem > nums[low]){
                low++;
            }
            nums[high] = nums[low];
        }
        nums[low] = tem;
        return low;
    }


//    private static void quickSort(int[] nums, int low, int high) {
//        if (low >= high){
//            return;
//        }
//        int mid = getMid(nums,low,high);
//        quickSort(nums,low,mid-1);
//        quickSort(nums,mid+1,high);
//    }
//    private static int getMid(int[] nums, int low, int high) {
//        int tem = nums[low];
//        while (low<high){
//            while (high>low&&tem<=nums[high]){
//                high--;
//            }
//            nums[low] = nums[high];
//            while (low<high&&tem>=nums[low]){
//                low++;
//            }
//            nums[high] = nums[low];
//        }
//        nums[low] = tem;
//        return low;
//    }

}
